---
title: STL 演算法
---

C++ 標準模板庫 (STL) 提供了一組豐富的通用演算法，這些演算法作用於元素範圍。這些演算法旨在高效且透過迭代器與各種容器類型配合使用。它們提供了強大的排序、搜尋、轉換和資料操作功能，通常比手動實作提供更優化的解決方案。本模組將這些演算法與常見的 JavaScript 陣列方法進行比較。

## 演算法庫概述

STL 演算法通常位於 `<algorithm>` 標頭中。它們是通用的，這表示它們可以與不同的資料類型和容器類型配合使用，只要提供的迭代器符合演算法的要求即可。演算法與容器的分離是 STL 的一個關鍵設計原則，促進了可重用性和靈活性。

## 排序演算法

排序演算法以特定順序排列元素。

### `std::sort`

*   預設情況下，以升序排序範圍內的元素。
*   通常使用內省排序 (快速排序、堆積排序和插入排序的混合) 實現平均 O(N log N) 的複雜度。

<UniversalEditor title="排序比較" compare={true}>
```javascript !! js
// JavaScript: Array.prototype.sort()
let numbers = [5, 2, 8, 1, 9];
numbers.sort((a, b) => a - b); // 升序排序
console.log(numbers); // [1, 2, 5, 8, 9]

let words = ["banana", "apple", "cherry"];
words.sort(); // 字典序排序
console.log(words); // ["apple", "banana", "cherry"]
```

```cpp !! cpp
// C++: std::sort
#include <iostream>
#include <vector>
#include <algorithm> // For std::sort
#include <string>

int main() {
  std::vector<int> numbers = {5, 2, 8, 1, 9};
  std::sort(numbers.begin(), numbers.end()); // 升序排序
  // for (int n : numbers) { std::cout << n << " "; }
  // std::cout << std::endl; // 輸出: 1 2 5 8 9

  std::vector<std::string> words = {"banana", "apple", "cherry"};
  std::sort(words.begin(), words.end()); // 字典序排序
  // for (const std::string& w : words) { std::cout << w << " "; }
  // std::cout << std::endl; // 輸出: apple banana cherry

  return 0;
}
```
</UniversalEditor>

### `std::stable_sort`

*   在排序元素的同時，保留等效元素的相對順序。
*   通常使用合併排序或類似演算法，複雜度為 O(N log N)。

### `std::partial_sort`

*   僅排序範圍的一部分，特別是前 `n` 個元素。

## 搜尋演算法

搜尋演算法在範圍內尋找元素。

### `std::find`

*   在範圍內搜尋值的第一次出現。
*   返回指向第一個匹配元素的迭代器，如果未找到則返回 `last`。
*   線性搜尋，O(N) 複雜度。

<UniversalEditor title="搜尋比較" compare={true}>
```javascript !! js
// JavaScript: Array.prototype.includes(), Array.prototype.indexOf()
let data = [10, 20, 30, 40, 50];

console.log(data.includes(30)); // true
console.log(data.includes(100)); // false

console.log(data.indexOf(20)); // 1
console.log(data.indexOf(99)); // -1
```

```cpp !! cpp
// C++: std::find
#include <iostream>
#include <vector>
#include <algorithm> // For std::find

int main() {
  std::vector<int> data = {10, 20, 30, 40, 50};

  auto it = std::find(data.begin(), data.end(), 30);
  // if (it != data.end()) {
  //   std::cout << "Found 30 at index: " << std::distance(data.begin(), it) << std::endl;
  // } else {
  //   std::cout << "30 not found." << std::endl;
  // }

  it = std::find(data.begin(), data.end(), 100);
  // if (it != data.end()) {
  //   std::cout << "Found 100." << std::endl;
  // } else {
  //   std::cout << "100 not found." << std::endl;
  // }

  return 0;
}
```
</UniversalEditor>

### `std::binary_search`

*   檢查**已排序**範圍中是否存在元素。
*   如果找到則返回 `true`，否則返回 `false`。
*   二分搜尋，O(log N) 複雜度。

### `std::lower_bound` / `std::upper_bound`

*   `lower_bound`：返回指向已排序範圍中第一個不小於 (即大於或等於) 給定值的元素的迭代器。
*   `upper_bound`：返回指向已排序範圍中第一個大於給定值的元素的迭代器。

## 修改演算法

修改演算法會更改範圍內的元素。

### `std::copy`

*   將元素從一個範圍複製到另一個範圍。

<UniversalEditor title="複製比較" compare={true}>
```javascript !! js
// JavaScript: Array.prototype.slice(), 展開運算子
let source = [1, 2, 3];
let destination = [...source]; // 使用展開運算子複製
console.log(destination); // [1, 2, 3]

let part = source.slice(0, 2); // 複製一部分
console.log(part); // [1, 2]
```

```cpp !! cpp
// C++: std::copy
#include <iostream>
#include <vector>
#include <algorithm> // For std::copy

int main() {
  std::vector<int> source = {1, 2, 3};
  std::vector<int> destination(source.size()); // 預先分配空間
  std::copy(source.begin(), source.end(), destination.begin());
  // for (int n : destination) { std::cout << n << " "; }
  // std::cout << std::endl; // 輸出: 1 2 3

  std::vector<int> part(2);
  std::copy(source.begin(), source.begin() + 2, part.begin());
  // for (int n : part) { std::cout << n << " "; }
  // std::cout << std::endl; // 輸出: 1 2

  return 0;
}
```
</UniversalEditor>

### `std::transform`

*   對範圍中的每個元素應用函式，並將結果儲存在另一個範圍中。

<UniversalEditor title="轉換比較" compare={true}>
```javascript !! js
// JavaScript: Array.prototype.map()
let numbers = [1, 2, 3];
let doubled = numbers.map(num => num * 2);
console.log(doubled); // [2, 4, 6]
```

```cpp !! cpp
// C++: std::transform
#include <iostream>
#include <vector>
#include <algorithm> // For std::transform

int main() {
  std::vector<int> numbers = {1, 2, 3};
  std::vector<int> doubled(numbers.size());

  std::transform(numbers.begin(), numbers.end(), doubled.begin(),
                 [](int num) { return num * 2; }); // Lambda 函式

  // for (int n : doubled) { std::cout << n << " "; }
  // std::cout << std::endl; // 輸出: 2 4 6

  return 0;
}
```
</UniversalEditor>

### `std::replace`

*   將範圍中特定值的所有出現替換為另一個值。

## 數值演算法

數值演算法位於 `<numeric>` 標頭中。

### `std::accumulate`

*   計算範圍中元素的總和，或累加應用二元運算。

<UniversalEditor title="累加比較" compare={true}>
```javascript !! js
// JavaScript: Array.prototype.reduce()
let numbers = [1, 2, 3, 4, 5];
let sum = numbers.reduce((acc, current) => acc + current, 0);
console.log(sum); // 15
```

```cpp !! cpp
// C++: std::accumulate
#include <iostream>
#include <vector>
#include <numeric> // For std::accumulate

int main() {
  std::vector<int> numbers = {1, 2, 3, 4, 5};
  int sum = std::accumulate(numbers.begin(), numbers.end(), 0); // 初始值 0
  // std::cout << "Sum: " << sum << std::endl; // 輸出: 15

  return 0;
}
```
</UniversalEditor>

### `std::inner_product`

*   計算兩個範圍的內積 (對應元素乘積的總和)。

## 與 JavaScript 陣列方法的比較

JavaScript 的 `Array.prototype` 提供了許多內建方法，這些方法提供了與 STL 演算法類似的功能。但是，存在關鍵差異：

| 特性           | JavaScript 陣列方法                 | C++ STL 演算法                       |
| :---------------- | :--------------------------------------- | :--------------------------------------- |
| **通用性**    | 透過動態類型實現              | 透過模板和迭代器實現     |
| **類型安全**   | 運行時類型檢查                    | 編譯時類型檢查               |
| **性能**   | 通常內部優化，但動態類型/GC 帶來開銷 | 高度優化，直接記憶體存取，編譯時優化 |
| **靈活性**   | 僅限於陣列 (和類似陣列的物件) | 適用於任何提供迭代器的容器 |
| **錯誤處理**| 拋出運行時錯誤                    | 類型不匹配的編譯時錯誤，無效迭代器的運行時錯誤 |

## 演算法性能分析

STL 演算法通常經過高度優化，並提供強大的性能保證。它們的複雜度通常以其操作範圍中的元素數量 (N) 表示。

*   **O(N) (線性)：** `std::find`、`std::copy`、`std::transform`、`std::accumulate`。
*   **O(N log N) (對數線性)：** `std::sort`、`std::stable_sort`。
*   **O(log N) (對數)：** `std::binary_search` (在已排序範圍上)。

了解這些複雜度有助於為給定任務選擇最合適的演算法，尤其是在性能關鍵的應用程式中。

---

### 練習題：
1.  解釋 `std::sort` 和 `std::stable_sort` 之間的區別。何時會優先選擇其中一個？
2.  C++ 中的 `std::transform` 與 JavaScript 的 `Array.prototype.map()` 如何比較？提供一個簡單的範例，其中使用 `std::transform` 將向量中的每個元素加倍。
3.  討論使用 STL 演算法相對於在 C++ 中手動實作類似功能的優點。

### 專案構想：
*   創建一個 C++ 程式，從檔案中讀取數字列表，對其進行排序，移除重複項，然後計算其總和和平均值。使用適當的 STL 容器和演算法 (`std::vector`、`std::sort`、`std::unique`、`std::accumulate`)。將其性能與手動實作的排序和求和版本進行比較。
